//#region 回文 系列

/** 647. 回文子串的个数
 * - 给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目 
 * - 还有双指针解法
 */
export function countSubstrings(s: string = "abc"): number {
    const length = s.length
    /**  https://programmercarl.com/0647.回文子串.html#思路
    * 我们在判断字符串S是否是回文，那么如果我们知道 s[1]，s[2]，s[3] 这个子串是回文的，那么只需要比较 s[0]和s[4]这两个元素是否相同，如果相同的话，这个字符串s 就是回文串。
    * 此时我们就能找到一种递归关系，也就是判断一个子字符串（字符串的下表范围[i,j]）是否回文，依赖于，子字符串（下表范围[i + 1, j - 1]）） 是否是回文。
    * 
    * - dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。
    * 
    * - 当s[i]与s[j]不相等，那没啥好说的了，dp[i][j]一定是false。
    * 
    * - 当s[i]与s[j]相等时，这就复杂一些了，有如下三种情况：
    * 1. 下标i与j是同一个位置，例如都指向同一个a，当然是回文子串
    * 2. 下标i与j相差为1，例如aa，也是回文子串
    * 3. 下标i与j相差大于1时，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。
    * 
    * - 遍历顺序：观察上面相等时的第三种情况的递推公式，可以发现推导的数据来源于左下方，所以 i逆序 j正序 
    */
    const dp = Array.from({ length }, () => new Array<boolean>(length).fill(false))
    let res = 0
    for (let i = length - 1; i >= 0; i--) { //逆序
        for (let j = i; j < length; j++) { //正序且从 i 开始
            if (s[i] === s[j]) {
                if (j - i <= 1) {//情况1和2
                    res++
                    dp[i][j] = true
                } else if (dp[i + 1][j - 1]) {//情况3
                    res++
                    dp[i][j] = true
                }
            }
        }
    }
    return res
}
/**5. 最长回文子串 
 * - 给你一个字符串 s，找到 s 中最长的回文子串。 
 * - 思路是我自己仿造上面 647.回文子串的个数 的，时间复杂度和空间复杂度特别差，应该选用双指针写法
 * - 除此之外还有一个原因就是，我dp数组放的是字符串，而正常解法是布尔值，然后维护一个left和right，最后return s.subString(left, right) 即可 
 */
export function longestPalindrome(s: string = "babad"): string {
    const length = s.length
    /**dp[i][j]：区间i,j 之间，如果是回文子串就是放入该串，不是的话就放空字符串 
     * - i在左，j在右
     * - dp[i][j] = dp[i + 1][j - 1] + 2  // dp[i][j] 依赖于内侧的dp，如 [0][3]依赖于[1][2]来判断是不是回文
     */
    const dp = Array.from({ length }, () => new Array<string>(length).fill(''))
    let res = ''
    for (let i = length - 1; i >= 0; i--) { //逆序
        for (let j = i; j < length; j++) { //正序且从 i 开始
            if (s[i] === s[j]) {
                if (j - i === 0) {//如果ij在一块
                    dp[i][j] = s[i]
                } else if (j - i === 1) {  //如果ij相邻
                    dp[i][j] = s[i] + s[j]
                }
                else if (dp[i + 1][j - 1]) { //如果上一个是回文串的话
                    dp[i][j] = s[i] + dp[i + 1][j - 1] + s[j]
                }
                console.log(dp);
                if (dp[i][j].length > res.length) res = dp[i][j]
            }
        }
    }

    return res

    // 中心扩散法

    /**得到以i j为中心的最长回文串 */
    function getPalindrome(i: number, j: number) {
        while (i >= 0 && j < s.length && s[i] === s[j]) {
            i--;
            j++
        }
        return s.slice(i + 1, j)
    }
    //遍历字符串，中心扩散找
    let res2 = ''
    for (let i = 0; i < s.length; i++) {
        //回文有两情况，abba和aba形式，找出最大的
        const s1 = getPalindrome(i, i)
        const s2 = getPalindrome(i, i + 1)
        const realStr = s1.length > s2.length ? s1 : s2
        if (realStr.length > res2.length) res2 = realStr
    }
    return res2
}
/** 516. 最长回文子序列 
 * - 给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
 * - 除了下面的正常动规解法，还有另类解法：把s反转后，求s和s反转的“最大公共子序列”的长度，就是结果 （1143题）
 */
export function longestPalindromeSubseq(s: string = "bbbab"): number {
    const length = s.length
    /**
     * dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。
     * - 如果s[i]与s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2;（看定义，长度是+2的）
     * - 如果s[i]与s[j]不相同，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。
     * - 取最大的，即：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
     * 
     * - 初始化：地推公式计算不到ij相同的情况，需要手动初始化。
     * 
     * - 遍历顺序：根据公式，依赖于 i + 1、j-1的数据，也就是依赖于左下方，i逆序 j正序
     */
    const dp = Array.from({ length }, () => new Array<number>(length).fill(0))
    for (let i = 0; i < length; i++) dp[i][i] = 1;
    for (let i = length - 1; i >= 0; i--) {
        for (let j = i + 1; j < length; j++) {
            if (s[i] == s[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[0][length - 1] //返回右上角的值
}
//#endregion
